"""
例11　最接近target的值
1．问题描述
给出一个数组，在数组中找到2个数，使得它们的和最接近但不超
过目标值，返回它们的和。
2．问题示例
输入target=15，array=[1，3，5，11，7]，输出14，11+3=14。输入
target=16和array=[1，3，5，11，7]，输出16，11+5=16。
"""


# 定义一个函数，输入目标值target和数组array，返回最接近目标值且不超过目标值的两个数之和
def closest_sum_not_exceeding_target(target, array):
    # 先对数组进行排序
    sorted_array = sorted(array)

    # 初始化结果变量为无穷大，用于存储找到的最接近目标值且不超过目标值的和
    result = float('inf')
    current_sum = 0

    # 双指针法，一个指针在左边，一个指针在右边
    left, right = 0, len(sorted_array) - 1

    while left < right:
        current_sum = sorted_array[left] + sorted_array[right]

        # 如果当前和等于目标值，则直接返回
        if current_sum == target:
            return f'{sorted_array[left]} + {sorted_array[right]} = {current_sum}'

        # 如果当前和小于目标值且更接近目标值，则更新结果
        if current_sum < target and abs(target - current_sum) < abs(target - result):
            result = current_sum

        # 移动指针，根据当前和与目标值的关系调整
        if current_sum < target:
            left += 1
        else:  # 当前和大于目标值
            right -= 1

    # 返回找到的最接近目标值且不超过目标值的和
    return f'{sorted_array[left]} + {sorted_array[right]} = {result}'


# 测试示例
example1 = 12, [1, 3, 5, 11, 7]
example2 = 18, [1, 3, 5, 11, 7]

print(closest_sum_not_exceeding_target(*example1))  # 输出：14
print(closest_sum_not_exceeding_target(*example2))  # 输出：16
